With the proliferation of mobile applications, the demand for higher throughput of wireless systems is increasing at a staggering pace. The massive MIMO system is a key technology to handle orders of magnitude higher data traffic for the coming applications [1]. The massive MIMO technique is based on spatial multiplexing that enables multiple data streams to multiple UEs concurrently. The large number of antennas focusing energy into individual UEs brings huge improvements in throughput and radiated energy efficiency. To enable the gain of the large number of antennas, significant effort of computation is needed at each Base Station (BS), e.g., pre-coding matrix computation.
The concept of massive MIMO systems is to enable signals from all antennas adding up constructively at the desired UEs. To achieve this goal, the BS needs to first estimate the channel between each antenna and each UE, and then performs beamforming. One of the biggest challenges for massive MIMO systems is that the computation complexity of beamforming may be too high for real-time implementation. For example, with M BS antennas and K single-antenna UEs, employing Zero-Forcing (ZF) beamforming, the system needs to perform O(MK2) complex-valued multiplications and an inversion of a K×K matrix for every channel coherence bandwidth in the frequency domain and for every channel coherence time (e.g., one or more milliseconds) in the time domain.
Due to the superior performance over conjugate beamforming with the same number of served UEs on the same time-frequency resource, the ZF method has been considered as a promising method to achieve high throughput for many UEs. It has been shown that the ZF method is able to achieve the performance very close to the channel capacity in massive MIMO systems [1]. Previous inventions have been proposed to reduce the complexity of ZF pre-coding. In [2], a Neumann Series (NS) based method is proposed to improve the speed of matrix inversion. The NS based method was later improved with a higher probability to converge by our patent application PCT/US15/52386. To the best of our knowledge, no previous method has been proposed to reduce the complexity of the O(MK2) complex-valued multiplication. The overall ZF pre-coding consists of two stages, i.e., the matrix multiplication and the matrix inversion. Note that the complexity of matrix multiplication O(MK2) is much larger than the complexity of matrix inversion O(K3) since the value of M is always much larger than K in massive MIMO systems. Therefore, it is very important to design an efficient method to reduce the complexity of matrix multiplication.
One embodiment of this invention is an innovative method to reduce the complexity of matrix multiplication in pre-coding matrix computation for a massive MIMO system. The design consists of spatial Fast Fourier Transform (FFT) that converts each signal vector of signals at different BS antennas to a sparse one. The reason that the output of the spatial FFT is a sparse vector is because the arriving signals are from limited angles reflected by limited spatial reflectors. With these sparse vectors, the multiplication of two matrices, which are essentially multiplications of the vectors in the matrices, can be simplified since many entries of the vectors are almost zeros.
Another embodiment of this invention is to perform fast UE grouping using the spatial FFT method. In massive MIMO systems, since many UEs need to be served, they need to be scheduled into different groups so that each group is served on the same time-frequency resource. One general rule is to schedule low-correlated UEs in the same group, which is able to construct a diagonally dominant correlation matrix, for an easier NS implementation. With the spatial FFT method, the complexity of grouping is also reduced.